package com.lry.basic.algorithm.list;

import java.util.*;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/7/29
 */
public class LinkedList {
    //尾插法
    private ListNode create(int[]arr){
        if(arr==null||arr.length==0)return null;
        ListNode head = new ListNode(arr[0]);
        ListNode tail = head;
        for(int i=1;i<arr.length;i++){
            ListNode node = new ListNode(arr[i]);
            tail.next = node;
            tail = node;
        }
        return head;
    }
    private void print(ListNode head){
        while(head!=null){
            System.out.print(head.val+" ");
            head = head.next;
        }
        System.out.println();
    }
    private ListNode mergeTwoLists(ListNode l1,ListNode l2){
        if(l1==null&&l2==null)return null;
        if(l1==null&&l2!=null)return l2;
        if(l1!=null&l2==null)return l1;
        ListNode result = null;
        if(l1.val<l2.val){
            result = l1;
            l1 = l1.next;
        }else{
            result = l2;
            l2 = l2.next;
        }
        ListNode tail = result;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                tail.next = l1;
                tail = l1;
                l1 = l1.next;
            }else{
                tail.next = l2;
                tail = l2;
                l2 = l2.next;
            }
        }
        //可能还有一个链表非空
        while(l1!=null){
            tail.next = l1;
            tail = l1;
            l1 = l1.next;
        }
        while(l2!=null){
            tail.next = l2;
            tail = l2;
            l2 = l2.next;
        }
        return result;
    }
    private ListNode mergeKLists(ListNode[] lists) {
        if(lists==null||lists.length==0)return null;
        return mergeKLists(lists,0,lists.length-1);
    }
    private ListNode mergeKLists(ListNode[] lists,int low,int high) {
        if(low<high){
            int mid = (low+high)/2;
            return mergeTwoLists(mergeKLists(lists,low,mid),mergeKLists(lists,mid+1,high));
        }
        return lists[low];
    }

    /**
     * 反转单链表
     * @param head
     * @return
     */
    private ListNode reverseList(ListNode head){
        if(head==null)return null;
        ListNode next = head.next;
        head.next = null;
        ListNode nnext = null;
        while(next!=null){
            nnext = next.next;
            next.next = head;
            head = next;
            next = nnext;
        }
        return head;
    }
    //0(1)删除节点
    private void del(ListNode head,ListNode del) {
        if(del==null)return;
        if(del.next!=null){
            del.val = del.next.val;
            del.next = del.next.next;
        }else{//删除的节点是尾节点
            while(head.next!=del){
                head = head.next;
            }
            head.next = null;
        }
    }
    public ListNode removeElements(ListNode head, int val) {
        if(head==null)return null;
        //构造空节点
        ListNode nil = new ListNode(-val);
        ListNode res = nil;
        nil.next = head;
        while(nil!=null){
            if(nil.next!=null&&nil.next.val==val){
                nil.next = nil.next.next;
            }else{
                nil = nil.next;
            }
        }
        return res.next;
    }
    //给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
    //单纯的改变节点内部的值
    private void swapPairs(ListNode head) {
        int temp = 0;
        while(head!=null&&head.next!=null){
            temp = head.val;
            head.val = head.next.val;
            head.next.val = temp;
            head = head.next.next;
        }
    }
    //给定一个链表，两两交换其中相邻的节点，并返回交换后的链表
    //实际的进行节点交换
    private ListNode swapPair(ListNode head){
        if(head==null||head.next==null)return head;
        ListNode res = head.next;
        ListNode p,q,r= null;
        while(head!=null&&(p=head.next)!=null){
            q = p.next;
            if(q!=null){
                r = q.next;
            }else{
                r= null;
            }
            p.next = head;
            if(r==null){
                head.next = q;
            }else {
                head.next = r;
            }
            head = q;
        }
        return res;
    }
    //判断一个链表是否是回文
    //o(n)时间复杂度，0（n）空间复杂度
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head = head.next;
        }
        int [] res  = new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return isPalindrome(res);
    }
    private boolean isPalindrome(int[]objs){
        boolean flag = true;
        for(int i=0;i<objs.length/2;i++){
            if(objs[i]!=objs[objs.length-1-i]){
                flag = false;
            }
        }
        return flag;
    }
    //判断一个链表是否是回文
    //o(n)时间复杂度，0（1）空间复杂度
    public boolean isPalindrome1(ListNode head) {
        boolean isEven = isEven(head);
        if(head==null||head.next==null)return true;
        ListNode mid = mid(head);
        ListNode right=mid.next,left = mid;
        //反转左边链表
        ListNode next = head.next;
        ListNode nnext = null;
        head.next = null;
        while(next!=null){
            if(isEven) {//偶数
                if(head==left)break;
            }else{
                if(next==left)break;
            }
            nnext = next.next;
            next.next = head;
            head = next;
            next = nnext;
        }
        //左边链表和右边链表一一比对
        boolean f = true;
        while(head!=null&&right!=null){
            if(head.val!=right.val){
                f=false;
                break;
            }
            head = head.next;
            right = right.next;
        }
        return f;
    }
    //链表长度是否是偶数
    public boolean isEven(ListNode head){
        int size = 0;
        while(head!=null){
            ++size;
            head = head.next;
        }
        return size%2==0?true:false;
    }
    public ListNode mid(ListNode head){
        ListNode quick = head;
        ListNode slow = head;
        while(quick.next!=null&&quick.next.next!=null){
            slow = slow.next;
            quick =  quick.next.next;
        }
        return slow;
    }
    //判断单链表是否有环  低效
    public boolean hasCycle(ListNode head) {
        List<ListNode>list = new ArrayList<>();
        boolean f= false;
        while(head!=null){
            if(list.contains(head)){
                f = true;
                break;
            }
            list.add(head);
            head=head.next;
        }
        return f;
    }
    //双指针法,设置步长不同的指针，终有一天会相遇
    public boolean hasCycle1(ListNode head){
        ListNode quick = head,slow = head;
        while(quick!=null&&quick.next!=null){
            quick = quick.next.next;
            slow = slow.next;
            if(quick==slow){
                return true;
            }
        }
        return false;
    }
    //反转从第m个节点到第n个节点的链表
    public ListNode reverseBetween(ListNode head, int m, int n) {
        //这些情况不反转
        if(m<0||n<0||n<=m||head==null||head.next==null){
            return head;
        }
        int size=0;
        //定位到m
        ListNode mNode = head;
        //m的前驱
        ListNode mNodePre = null;
        //保存m位置的节点
        ListNode saveMNode = null;
        while(mNode!=null){
            ++size;
            if(size==m)break;
            mNodePre = mNode;
            mNode = mNode.next;
        }
        saveMNode = mNode;
        if(mNode==null){//说明m太大了
            return head;
        }
        //和普通反转链表算法一样
        ListNode mNextNode = mNode.next;
        ListNode mNNextNode = null;
        mNode.next = null;
        while(mNextNode!=null){
            mNNextNode = mNextNode.next;
            mNextNode.next = mNode;
            mNode = mNextNode;
            mNextNode = mNNextNode;
            ++size;
            if(size==n)break;
        }
        //补链
        if(mNodePre!=null){
            mNodePre.next = mNode;
        }
        else{
            head = mNode;
        }
        //补链
        saveMNode.next = mNNextNode;
        return head;
    }
    //找到相交链表的相交节点
    //由于我的链表的构造方式，在这个程序中不可能存在相交链表
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null)return null;
        ListNode a = headA,b = headB;
        while(a!=b){
            a = a==null?headB:a.next;
            b = b==null?headA:b.next;
        }
        return a;
    }
    //删除排序链表重复元素，重复的只留一个
    public ListNode deleteDub(ListNode head){
        if(head==null)return null;
        ListNode res = head;
        int val = res.val;
        ListNode t = res.next;
        while(t!=null){
            if(val!=t.val){
                res.next = t;
                res = t;
                val = t.val;
            }
            t= t.next;
        }
        res.next = null;//防止1->1->1这种情况
        return head;
    }
    //删除排序链表重复元素，重复的一个不留
    public ListNode delAllDub(ListNode head){
        if(head==null)return null;
        //res去链接下一个节点，result是最后返回的头节点
        ListNode res = null,result = null;
        boolean flag = true;//第一次标志
       while(head!=null){
           if(head.next==null){//head是尾节点
               if(res==null){//说明删到最后只剩下尾节点符合要求
                   result = head;
               }else{//链接尾节点
                   res.next = head;
               }
               head = head.next;//跳出while循环
           } else if(head.val!=head.next.val){
               if(flag){//找到头，第一次
                   res = head;
                   result = res;//头节点
                   flag = false;//进else
               }else{
                   res.next = head;//除了第一次，都是next
                   res = head;
               }
               head = head.next;
           }else{//跳过不符合的节点
                int val = head.val;
               while(head!=null&&head.val==val){
                   head = head.next;
               }
               //1->2->2 防止这种情况不断链
               if(res!=null)
               res.next = null;
           }
       }
       return result;
    }

    /**
     * 循环右移链表
     * k=0，不移动
     * k>0,向右移动k
     * k<0，向左移动|k|
     * k可以是int表示的任何值
     * @param head
     * @param k
     * @return
     */
    public ListNode rotate(ListNode head,int k){
        if(head==null||k==0)return head;
        int size = size(head);
        if(size==1)return head;
        k = k%size;
        if(k==0)return head;
        if(k>0){//右移 找倒k
            ListNode slow = head;//慢指针
            ListNode slowPre = null;//慢指针的前驱
            ListNode quick = head;//快指针
            ListNode quickPre = null;//快指针的前驱
            while(k-->0){//快指针先行k步
                quickPre = quick;
                quick = quick.next;
            }
            while(quick!=null){
                quickPre = quick;
                quick = quick.next;
                slowPre = slow;
                slow = slow.next;
            }
            slowPre.next = null;
            quickPre.next = head;
            return slow;
        }else{//左移 找顺k
            k = Math.abs(k);
            ListNode result = null;
            ListNode cur = head;
            ListNode curPre = null;
            while(k-->0){
                curPre = cur;
                cur = cur.next;
            }
            result = cur;
            curPre.next = null;
            while(cur.next!=null){
                cur = cur.next;
            }
            cur.next = head;
            return result;
        }
    }
    public int size(ListNode head){
        int size = 0;
        while(head!=null){
            ++size;
            head = head.next;
        }
        return size;
    }

    public ListNode reverse(ListNode head){
        if(null==head||null==head.next)
            return head;
        ListNode rNode = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return rNode;
    }

    //每k个一组反转链表
    public ListNode reverseK(ListNode head,int k){
        if(null==head||k<=0){
            return head;
        }
        ListNode tmp = head;
        for(int i=1;i<k&&tmp!=null;i++){
            tmp = tmp.next;
        }
        if(tmp==null){
            return head;
        }

        ListNode t = tmp.next;
        tmp.next = null;

        ListNode rNode = reverse(head);
        ListNode rKNode = reverseK(t,k);
        head.next = rKNode;
        return rNode;
    }


    public ListNode sortList(ListNode head) {
        if(null==head||null==head.next){
            return head;
        }
        return mergeSort(head);
    }

    public ListNode mergeSort(ListNode head){
        ListNode quick = head;
        ListNode slow = head;
        ListNode slowPre = null;
        while(quick!=null&&quick.next!=null){
            quick = quick.next.next;
            slowPre = slow;
            slow = slow.next;
        }
        if(slowPre!=null)
        slowPre.next = null;
        return merge(mergeSort(head),mergeSort(slow));
    }

    public ListNode cut(ListNode head,int l){
        ListNode t = head;
        while(t!=null&&l>0){
            t = t.next;
            --l;
        }
        return t;
    }

    public ListNode merge(ListNode l1,ListNode l2){
        ListNode result = new ListNode(0);
        ListNode t = result;

        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                t.next = l1;
                t = l1;
                l1 = l1.next;
            }else{
                t.next = l2;
                t = l2;
                l2 = l2.next;
            }
        }
        if(l1!=null){
            t.next = l1;
        }
        if(l2!=null){
            t.next = l2;
        }
        return result.next;
    }

//    定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
//    你应当保留两个分区中每个节点的初始相对位置。
//    示例:
//    输入: head = 1->4->3->2->5->2, x = 3
//    输出: 1->2-->2->4->3->5
    public ListNode partition(ListNode head,int x){
        if(null==head)
            return head;
        ListNode l1 = new ListNode(0);
        ListNode tL1 = l1;

        ListNode l2 = new ListNode(0);
        ListNode tL2 = l2;

        while(head!=null){
            if(head.val<x){
                tL1.next = head;
                tL1 = tL1.next;
            }else{
                tL2.next = head;
                tL2 = tL2.next;
            }
            head = head.next;
        }
        tL2.next = null;
        tL1.next = l2.next;
        return l1.next;
    }

//    给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
//    请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
//    示例 1:
//    输入: 1->2->3->4->5->NULL
//    输出: 1->3->5->2->4->NULL
//
//    示例 2:
//    输入: 2->1->3->5->6->4->7->NULL
//    输出: 2->3->6->7->1->5->4->NULL
//
//    说明:
//    应当保持奇数节点和偶数节点的相对顺序。
//    链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

    public ListNode oddEvenList(ListNode head) {
        if(null==head||null==head.next)
            return head;

        ListNode l1 = new ListNode(0);//存奇数
        ListNode tl1 = l1;

        ListNode l2 = new ListNode(0);//存偶数
        ListNode tl2 = l2;

        boolean isOld = true;//是否是奇
        while(head!=null){
            if(isOld){
                tl1.next = head;
                tl1 = tl1.next;
            }else{
                tl2.next = head;
                tl2 = tl2.next;
            }
            isOld = !isOld;
            head = head.next;
        }

        tl2.next = null;
        tl1.next = l2.next;
        return l1.next;
    }

//    给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
//    将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
//    你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
//
//    示例 1:
//    给定链表 1->2->3->4, 重新排列为 1->4->2->3.
//
//    示例 2:
//    给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
    //快慢指针找中点，反转右边的链，把右边链加入到左边链
    public void reorderList(ListNode head) {
        if(null==head||null==head.next)
            return;

        ListNode quick = head;
        ListNode slow = head;
        while(quick!=null&&quick.next!=null&&quick.next.next!=null){
            quick = quick.next.next;
            slow = slow.next;
        }

        ListNode right = slow.next;
        slow.next = null;

        ListNode rNode = reverse(right);

        ListNode t = head;
        while(t!=null&&rNode!=null){
            ListNode rt = rNode.next;
            ListNode tt = t.next;

            rNode.next = t.next;
            t.next = rNode;

            t = tt;
            rNode = rt;
        }

    }


//    给定两个用链表表示的整数，每个节点包含一个数位。
//    这些数位是反向存放的，也就是个位排在链表首部。
//    编写函数对这两个整数求和，并用链表形式返回结果。
//
//    示例：
//    输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
//    输出：2 -> 1 -> 9，即912
//

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int jin = 0;
        ListNode result = new ListNode(0);
        ListNode ans = result;
        while(l1!=null||l2!=null){
            int sum=0;
            if(l1==null){
                sum =  jin+l2.val;
                l2=l2.next;
            }else if(l2==null){
                sum =  jin+l1.val;
                l1=l1.next;
            }else{
                sum =  l1.val+l2.val+jin;
                l1=l1.next;
                l2=l2.next;
            }
            int mod = sum%10;
            jin = sum/10;
            ListNode t = new ListNode(mod);
            ans.next = t;
            ans = ans.next;
        }
        if(jin>0){
            ans.next = new ListNode(jin);
        }
        return result.next;
    }

//    进阶：假设这些数位是正向存放的，请再做一遍。并且不允许l1和l2反转
    //    示例：
//    输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
//    输出：9 -> 1 -> 2，即912
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer>s2 = new Stack<>();
        while(l1!=null){
            s1.push(l1.val);
            l1 = l1.next;
        }
        while(l2!=null){
            s2.push(l2.val);
            l2 = l2.next;
        }

        int jin = 0;
        ListNode result = new ListNode(0);

        while(!s1.isEmpty()||!s2.isEmpty()){
            int sum = jin;
            if(!s1.isEmpty()){
                sum+=s1.pop();
            }
            if(!s2.isEmpty()){
                sum+=s2.pop();
            }
            jin = sum/10;
            int mod = sum%10;
            ListNode node = new ListNode(mod);
            node.next = result.next;
            result.next = node;
        }
        if(jin>0){
            ListNode node = new ListNode(jin);
            node.next = result.next;
            result.next = node;
        }
        return result.next;

    }



    //    给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
//    输入: 1->1->2
//    输出: 1->2
    public ListNode deleteDuplicates(ListNode head) {
        if(null==head||head.next==null)
            return head;

        ListNode p = head;
        ListNode q = p.next;
        while(q!=null){
            if(p.val==q.val){
                p.next = q.next;
                q = q.next;
            }else{
                p = p.next;
                q = q.next;
            }
        }
        return head;
    }

    //重复元素全部删除
    public ListNode deleteDuplicates2(ListNode head) {
        if(null==head||head.next==null)
            return head;

        ListNode dummy = new ListNode(0);
        ListNode td = dummy;

        ListNode p = head;
        ListNode q = p.next;

        while(p!=null){
            if(q==null){
                ListNode t = p;
                p=p.next;
                t.next = null;
                td.next = t;
                td = td.next;

            }else if(p.val==q.val){
                int x = p.val;
                while(p!=null&&p.val==x){
                    if(p!=null)
                        p = p.next;
                    if(q!=null)
                        q = q.next;
                }
            }else{
                ListNode t = p;
                p=p.next;
                t.next = null;
                td.next = t;
                td = td.next;

                q = q.next;
            }
        }
        return dummy.next;
    }
//    public Node copyRandomList(Node head) {
//        if(null==head){
//            return head;
//        }
//        Node node = head;
//        Map<Node,Node> map = new HashMap<>();
//        while(node!=null){
//            Node clone = new Node(node.val);
//            map.put(node,clone);
//            node = node.next;
//        }
//        node = head;
//
//        while(node!=null){
//            map.get(node).next = map.get(node.next);
//            map.get(node).random = map.get(node.random);
//            node = node.next;
//        }
//        return map.get(head);
//    }

    public int[] nextLargerNodes(ListNode head) {
        if(head==null)
            return new int[0];

        List<Integer> list = new ArrayList();
        while(head!=null){
            list.add(head.val);
            head = head.next;
        }

        Integer[] nums= list.toArray(new Integer[0]);

        int[] dp = new int[nums.length];

        for(int i=nums.length-2;i>=0;i--){
            if(nums[i]<nums[i+1]){
                dp[i] = nums[i+1];
            }else if(nums[i]==nums[i+1]){
                dp[i] = dp[i+1];
            }else{
                int min = 0;
                for(int j=i+1;j<dp.length;j++){
                    if(dp[j]>nums[i]){
                        min = dp[j];
                        break;
                    }else if(dp[j]==0){
                        break;
                    }
                }
                dp[i] = min;
            }
        }
        return dp;
    }

    public int[] nextLargerNodes2(ListNode head) {
        if(head==null)
            return new int[0];

        List<Integer> list = new ArrayList();
        while(head!=null){
            list.add(head.val);
            head = head.next;
        }
        int[] nums = list.stream().mapToInt(Integer::valueOf).toArray();

        Stack<Integer> stack = new Stack();

        for(int i=0;i<nums.length;i++){
            while(!stack.isEmpty()&&nums[stack.peek()]<nums[i]){
                nums[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            nums[stack.pop()] = 0;
        }
        return nums;
    }

//    给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
//    删除完毕后，请你返回最终结果链表的头节点。
//    你可以返回任何满足题目要求的答案。
//   注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。
//    示例 1：
//    输入：head = [1,2,-3,3,1]
//    输出：[3,1]
//    提示：答案 [1,2,1] 也是正确的。
//
//    示例 2：
//    输入：head = [1,2,3,-3,4]
//    输出：[1,2,4]
//
//    示例 3：
//    输入：head = [1,2,3,-3,-2]
//    输出：[1]

    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        Map<Integer, ListNode> map = new HashMap<>();

        // 首次遍历建立 节点处链表和<->节点 哈希表
        // 若同一和出现多次会覆盖，即记录该sum出现的最后一次节点
        int sum = 0;
        for (ListNode d = dummy; d != null; d = d.next) {
            sum += d.val;
            map.put(sum, d);
        }

        // 第二遍遍历 若当前节点处sum在下一处出现了则表明两结点之间所有节点和为0 直接删除区间所有节点
        sum = 0;
        for (ListNode d = dummy; d != null; d = d.next) {
            sum += d.val;
            d.next = map.get(sum).next;
        }

        return dummy.next;
    }

    //数组，对象，链表，在函数里面可以更改值
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();
        ListNode l1 = ll.create(new int[]{1,3,5});
        ListNode l2 = ll.create(new int[]{2,4,6});
        ListNode mergeTwoLists = ll.mergeTwoLists(l1,l2);
        ll.print(mergeTwoLists);

        ListNode l3 = ll.create(new int[]{7,9,11});
        ListNode l4 = ll.create(new int[]{8,10,12});
        ListNode[] ListNodes = new ListNode[]{l3,l4};
        ListNode mergeKLists = ll.mergeKLists(ListNodes);
        ll.print(mergeKLists);

        ListNode l5 = ll.create(new int[]{1,2,3,4,5});
        ll.print(ll.reverseList(l5));

        ListNode l6 = ll.create(new int[]{1,2,3,4,5});
        ll.del(l6,l6.next.next);
        ll.print(l6);

        ListNode l7 = ll.create(new int[]{1,2,3,4,5});
        ll.swapPairs(l7);
        ll.print(l7);

        ListNode l8 = ll.create(new int[]{1,2,3,4,5});
        ll.print(ll.swapPair(l8));

        ListNode l9 = ll.create(new int[]{1,2,3,2,1});
        System.out.println(ll.isPalindrome(l9));

        ListNode l10 = ll.create(new int[]{1,2,2,1});
        System.out.println(ll.isPalindrome1(l10));

        ListNode l11 = ll.create(new int[]{1,1});
        System.out.println(ll.removeElements(l11,1));

        ListNode l12 = ll.create(new int[]{1,2,3,4,5});
        ll.print(ll.delAllDub(ll.reverseBetween(l12,2,4)));

        ListNode l13 = ll.create(new int[]{1,2,2,3,3,4});
        ll.print(ll.delAllDub(l13));

        ListNode l14 = ll.create(new int[]{1,2,3,4});
        ll.print(ll.rotate(l14,-1));

        ListNode l15 = ll.create(new int[]{1,4,3,2,5,2});
        ll.print(ll.partition(l15,3));

        ListNode l16 = ll.create(new int[]{1,1,2,3,3,4,5,5});
        ll.deleteDuplicates2(l16);
    }


    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
